The present invention relates to computer graphics systems, and more particularly, to decompressing and rendering compressed three-dimensional geometry data.
In recent years, demand for high performance graphics systems that can render complex three-dimensional (3D) objects and scenes has increased substantially. This increase is at least in part due to new applications such as computer-generated animation for motion pictures, virtual reality simulators/trainers, and interactive computer games. These new applications place tremendous demands upon graphics systems. One area in which particularly high demands are placed on graphics systems is bandwidth. This is because 3D graphics data may be several orders of magnitude larger than comparable 2D graphics data. For example, simple 2D graphics data may simply include color information for each pixel displayed. In contrast, 3D graphics data may include x,y,z position information, normal information, color information, transparency information, texture map information, reflectivity information, and additional information. This information is collectively referred to herein as xe2x80x9cvertex component informationxe2x80x9d.
A number of different techniques have been proposed to reduce the bandwidth requirements of 3D graphics data. One such technique is known as geometry compression. One type of geometry compression is described in detail in U.S. Pat. No. 5,793,371, issued on Aug. 11, 1998, entitled xe2x80x9cMethod and Apparatus for Geometric Compression of Three-Dimensional Graphics Dataxe2x80x9d by Michael F. Deering, which is incorporated herein by reference in its entirety. Generally speaking, geometry compression relies upon reusing vertices (among other techniques) to reduce the size of the 3D graphics data. To describe a 3D object, a number of points (called vertices) are specified. Each vertex may have a number of attributes associated with it. For example, each vertex may have color information associated with it. Other attribute that may be associated with vertices are texture map coordinates, normals, color, and transparency information. For example, if a texture of marble is texture-mapped onto a sphere, each vertex on the sphere may have a texture map coordinate specifying how the texture should be applied (i.e., which part of the sample texture should be mapped to that particular vertex). A normal is a vector from the vertex that is perpendicular to the surface of the object at the vertex. This is illustrated in the 3D object of FIG. 1. The 3D object may be represented by a number of vertices (represented as dots in the figure). Normals for the object are represented by arrows that extend perpendicularly from the object""s surface at each vertex point.
Normals are vectors or directions in three-dimensional space. In the context of 3D graphics, normals (also called surface normals) may each indicate the local orientation of the surface of a 3D graphics object. Since the starting point of the vector is known from the xyz coordinates of the vertex, the normal may be specified with an x-component, a y-component, and a z-component (referred to as Nx, Ny, and Nz, respectively). In some embodiments, these components may be specified relative to the vertex. This embodiment is illustrated in FIG. 2. However, other forms for specifying normals are also possible. Furthermore, in some implementations the normal components are themselves normalized. A normalized normal is one in which the sum of the squares of Nx, Ny, and Nz equals a constant one.
In 3D graphics, vertices are typically grouped together to form polygons such as triangles, as shown in FIG. 3. By definition, a triangle has three vertices. However, many times triangles share vertices. In FIG. 3, vertices 1-2-3 form a first triangle and vertices 2-3-4 form a second triangle. Thus, vertices 2 and 3 are shared between the two triangles. 3D objects may be represented by specifying a number of triangles. This is shown in FIG. 4.
However, specifying all of the information associated with each vertex (e.g., xyz location, color, normal, etc.) every time a vertex is referenced as part of a triangle is inefficient. Instead, the information about a vertex can be stored (e.g., when it is first transmitted) for later use. Then, when the vertex is needed again for another triangle, the vertex may be read from storage instead of having to be re-transmitted. The vertex information may be stored in a xe2x80x9cmesh bufferxe2x80x9d and then reused. This may advantageously reduce the amount of information that must be transmitted and may thus save bandwidth. This is illustrated in FIG. 5.
To efficiently reuse vertices, the triangles may be organized into a mesh (e.g., a predetermined number of neighboring vertices. The mesh may then be encoded as one or more xe2x80x9ctriangle-stripsxe2x80x9d. For example, in FIG. 6 of the application, the triangle strip may start with the following triangles: 6,1,7; 1,7,2; 7,2,3; 7,3,4; 7,4,8; 4,8,5; et seq.
As this pattern shows, once the triangle strip is started many subsequent triangles may be specified using only a single new vertex. For example, after triangle 6,1,7 has been constructed, triangle 1,7,2 may be constructed using only one new vertex (i.e., vertex 2). Thus, each vertex in the triangle strip may describe from ⅓ to one triangle. For example, in the list above, vertex 6 describes ⅓ of triangle 6,1,7. Vertex 2 describes one triangle 1,7,2. In some cases, a vertex may even describe two or even more triangles.
While a number of different formats are possible, one type of generalized triangle strip may be defined as follows (encoding the 3D object from FIG. 6):
R6, O1,O7,O2,O3, M4, M8, O5,O9,O10, M11 O17, M16, M9, O15, O8, O7, M14, O13, M6, O12, M18, M19, M20, M14, O21, O15, O22, O16, O23, O17, O24, M30, M29, M28, M22, O21, M20, M27, O26, M19, O25, O18
In the notation above, R is a restart tag (indicating that a new mesh is beginning), O denotes replace oldest, and M denotes replace middle. The operation of this type of generalized triangle strip is illustrated in FIGS. 7A-7H.
In some embodiments, the terms xe2x80x9coldestxe2x80x9d and xe2x80x9cmiddlexe2x80x9d may be visualized as representing three registers that are used in forming triangles from the triangle strip representation. The sample encoding above is merely one nomenclature that may be used to represent how the vertices of the mesh are being encoded. Different implementations may use other nomenclatures. The example nomenclature uses letters (O and M) to indicate which vertex should be discarded from the three registers when forming a new triangle. O indicates the oldest vertex should be discarded. M indicates the middle vertex should be discarded. R indicates that a section of mesh is being started. This is used to clear the oldest, middle, and newest registers and the mesh buffer, if desired.
While this method reuses vertices, when vertex 8 is referenced a second time (i.e., by the command O8), the vertex is transmitted again. This retransmission of vertices may be reduced or avoided altogether by using a mesh buffer.
Using a similar nomenclature as in the previous example, a generalized triangle mesh utilizing a mesh buffer may be defined as follows (once again encoding the 3D object of FIG. 6):
R6p, O1, O7p, O2,O3, M4, M8p, O5, O9p, O10, M11, O17p, M16p, Mxe2x88x923, O15p, Oxe2x88x925, Oxe2x88x926, M14p, O13p, Mxe2x88x929, O12, M18p, M19p, M20p, Mxe2x88x925, O21p, Oxe2x88x9224, O22p, Oxe2x88x929, O23, Oxe2x88x9210, Oxe2x88x927, M30, M29, M28, Mxe2x88x921, Oxe2x88x922, Mxe2x88x923, M27, O26, Mxe2x88x924, O25, Oxe2x88x925
In this implementation, a trailing letter xe2x80x9cpxe2x80x9d denotes xe2x80x9cpush into mesh bufferxe2x80x9d. The number following a capital letter is a vertex number, and a negative number is the mesh buffer reference, in which xe2x80x9cxe2x88x921xe2x80x9d denotes the most recent pushed vertex.
Thus, geometry compression may explicitly push old vertices (e.g., vertices with a trailing letter xe2x80x9cpxe2x80x9d above) into a mesh buffer. These old vertices may be explicitly referenced when the old vertex is again needed. This approach provides a fine control that supports irregular meshes of nearly any shape. As used herein, the term xe2x80x9cmesh bufferxe2x80x9d shall refer to this queue, and the expression xe2x80x9cgeneralized triangle meshxe2x80x9d will refer to a combination of generalized triangle strips and mesh buffer references.
FIGS. 8A-8N illustrate one embodiment of this method graphically. The mesh buffer may be used to store designated vertices (i.e., those followed by a xe2x80x9cpxe2x80x9d). These vertices may later be read out of the mesh buffer (e.g., by a reference with a minus sign such as xe2x80x9cMxe2x88x923xe2x80x9d). This allows vertices to be reused from the mesh buffer instead of having to be retransmitted.
As previously noted, by reducing the size of the 3D graphic data bandwidth may be saved. For example, when programmers are creating a 3D virtual object to be used in a simulation, they may execute a compression program to determine how best to compress the 3D object. The compression program may tessellate or divide the surface of the object into a plurality of vertices, e.g., a NURBs (Non-Uniform Rational B-spline) object. The compression program may then divide the vertices into groups of generalized triangle meshes as described above. These meshes may then be compressed and encoded using a similar process to that described above. The compressed data may then be stored (e.g., on a CD-ROM or DVD-ROM) and/or transmitted (e.g., on the Internet). The bandwidth savings may also apply to buses used for transmission of the 3D geometry data within the graphics system itself.
FIG. 9 illustrates one embodiment of a graphics system 20 configured to utilize compressed 3D geometry data in generalized triangle mesh form. In this embodiment, transmission bandwidth across transmission medium 10 is saved by transmitting 3D graphics data in compressed form using geometry compression in generalized triangle mesh format.
Generally, compressed 3D geometry data is conveyed to graphics system 20 on input bus 10. Geometry decompressor 12 receives the compressed data and decompresses it. A mesh buffer 14 may be used to store vertices that will be reused. As previously described, mesh buffer references may be encoded within the compressed data to indicate which vertices will be reused and thus should be stored in the mesh buffer.
Once a geometric primitive such as a triangle is decompressed, it is conveyed to one of a plurality of transform and lighting processors 18A-N. The transform and lighting processors work independently and in parallel to perform the following functions: (a) transform the vertices forming primitive from their original coordinate reference frame (e.g., object space) into a common reference frame (e.g., world space or screen space); and (b) xe2x80x9clightxe2x80x9d each vertex by determining which light sources affect each vertex and how much they are affected.
Next, the transformed and lit triangles are conveyed to draw processor 22, which is configured to render the transformed and lit primitives and apply texture mapping (e.g., from texture map memory 24). In some embodiments, textures may instead be applied during the lighting process (collectively referred to as xe2x80x9cshadingxe2x80x9d). In some embodiments, when shading is used only micropolygons are drawn. Draw processor 22 is configured to rasterize the primitive into frame buffer 28. In most embodiments, frame buffer 28 is double buffered, with one buffer being draw into by draw processor 22 while the second buffer is being read by DACs 30. DACs 30 may read frame buffer 28 asynchronously with respect to draw processor 22. DACs 30 form an output video signal that is typically used to drive a display device such as a CRT monitor or LCD panel display.
For the reasons set forth above, the use of geometry compression is particularly advantageous in high performance graphics systems. However, further increases in performance are still demanded by modem applications. Thus, an efficient method for increasing the performance of graphics systems configured to utilize 3D graphics data that has been compressed into generalized triangle mesh format is desired. Furthermore, a graphics system capable of increased performance while utilizing compressed 3D geometry data is also desired.
The problems outlined above may, in part, be solved by a graphics system capable of delaying the formation of independent primitives until after transformation and/or lighting. In this way, vertices that are shared by more than one primitive have the potential to only be transformed and lit once, as opposed to being transformed and lit once for each triangle to which they belong. Transforming and or lighting may thus be performed on an individual vertex basis instead of on a geometric primitive basis. The individually transformed and lit vertices are then assembled into primitives for rendering.
In some embodiments, the graphics system may utilize a transformed vertex cache to store transformed and lit vertices. Each time a particular vertex is needed to form a geometric primitive, the vertex is read from the transformed vertex cache. Each vertex may be accessed using a tag assigned to the vertex during decompression.
In other embodiments, the graphics system may utilize a transformed vertex buffer that is similar to a mesh buffer in function. However, instead of storing vertices generated by the geometry decompressor, the transformed vertex buffer stores transformed and lit vertices. Mesh buffer references may be used by the transformed vertex buffer to determine which transformed and lit vertices should be stored in the transformed vertex buffer.